home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / util / pack / xpkrdcn21.lha / xpkRDCN / decompr.asm < prev    next >
Assembly Source File  |  1993-04-10  |  8KB  |  216 lines
  1. ;---------------------------------------------------------------------------;
  2. ;                                        ;
  3. ; This is the Ross Data Compression implemented in 68000 assembler          ;
  4. ; by Niklas Sjöberg, 2:203/415.3@Fidonet                    ;
  5. ;                                        ;
  6. ;                                        ;
  7. ; The source is fully in the Public Domain. If you think you can improve    ;
  8. ; some parts, feel free to modify the code. HOWEVER, be carefull to comment ;
  9. ; the parts where you change!                            ;
  10. ;                                        ;
  11. ; On entry:                                    ;
  12. ; a0 points to XpkSubParams                            ;
  13. ;---------------------------------------------------------------------------;
  14. ; 921205 - Due to optimization comments may seem a bit weird.. Just try
  15. ;          to read 5-10 lines at the time I'm sure you'll get it right..
  16. ; 930319 - Some optimizations by John Harris - jharris@cup.portal.com
  17. ;          All new opts marked with a '@'.  Cycle savings at 68000 level:
  18. ;          mloop is 8-10 cycles faster
  19. ;          path to s_loop is 18 cycles faster (outside the loop)
  20. ;           sr_loop is 32 cycles faster (outside)
  21. ;                  lr_loop is about 172 cycles faster, plus loop was changed to
  22. ;                          .l for 50 cycles faster every 4 bytes past cnt=23
  23. ;                  rl_loop is about 186 cycles faster, plus if src & dest are
  24. ;               either both even or both odd, the loop will use .l
  25. ;               for 58 cycles faster for every 4 bytes past cnt=19
  26. ; 930409 - (Niklas Sjoberg) Fixed some lethal bugs. Might take a few more
  27. ;          cycles but decompression won't be safe otherwise!
  28.  
  29.  
  30.     xdef _unpack            ; The only function called from
  31.                     ; the C-part of the library
  32.  
  33.     INCLUDE "libraries/xpksub.i"
  34.  
  35.     section    code
  36.  
  37. _unpack
  38.  
  39.     movem.l    a2-a6/d2-d7,-(SP)
  40.     move.l    xsp_InBuf(a0),a1    ; source pointer
  41.     move.l    xsp_InLen(a0),d1    ; source len
  42.     move.l    xsp_OutBuf(a0),a2    ; destination
  43.  
  44.     move.l    a1,a3            ; inbuff_idx  = inbuff
  45.     move.l    a2,a4            ; outbuff_idx = outbuff
  46.     move.l    a1,a5            ; inbuff_end  = inbuff
  47.     adda.l    d1,a5            ; + inbuff_len
  48.  
  49.     moveq    #0,d0
  50.     moveq    #0,d2
  51.     moveq    #0,d3
  52.     moveq    #0,d4
  53.     moveq    #0,d5
  54.     moveq    #0,d6
  55.     moveq    #0,d7
  56.     bra.s    mloop            ; @ New line.  mloop was restructured
  57. ;                ;to remove one branch, and adjust the others to
  58. ;                ;fall through most often instead of branching.
  59.  
  60. ;                               ; loopend moved here to make 1 branch short
  61. loopend
  62.     suba.l    a2,a4            ; This is the only exit point
  63.     move.l    a4,xsp_OutBufLen(a0)    ; return length to xpkmaster
  64.     movem.l    (SP)+,a2-a6/d2-d7
  65.     moveq    #0,d0
  66.     rts
  67.  
  68. new_ctrlbits                            ; @ New label, and moved routine
  69. ;    move.w    (a3)+,d2        ; new load ctrl-bits
  70.     move.b    (a3)+,-(SP)        ; Slightly faster than shifting
  71.     move.w    (SP)+,d2        ; and works on 68000....
  72.     move.b    (a3)+,d2
  73.                     ;
  74.     moveq    #15,d3            ; ctrl_mask = 0x8000
  75. ; This is ugly. Since (in worst case) we may overrun the buffer by
  76. ; 15 bytes by not checking source and source-end. However, empty
  77. ; control-word means that we only copy 15 in worst case. Hell, we
  78. ; have 256 XPK_MARGIN bytes to play with :=) (I hope...)
  79.     cmp.l    a5,a3            ; main-loop. Go on until end of
  80.     bge.s    loopend            ; source buffer
  81.     btst    d3,d2                   ; @ These two lines are duplicated
  82.     bne.s    crunched        ;   for branch efficiency
  83.  
  84. copy_char                ; @ New label
  85.     move.b    (a3)+,(a4)+        ; otherwise, copy char and advance
  86. ;    bra.s    mloop            ; @ This line removed
  87. mloop
  88.     subq.b    #1,d3
  89. ;    lsr.w    #1,d3            ; Check if we need to get a load of
  90.                     ; control bits
  91.     bmi.s    new_ctrlbits        ; @ Changed branch priority
  92.  
  93. ;    move.w    d2,d7            ; If bits & mask turns out to be one
  94. ;    and.w    d3,d7            ; then data is compressed
  95.     btst    d3,d2
  96.     beq.s    copy_char               ; @ Changed branch priority
  97.  
  98. crunched
  99. ;                ;@d4 only needs to be word extended for s_loop,
  100. ;                ;so I removed moveq #0 and added ext.w at s_loop
  101.  
  102.     moveq    #0,d4            ; First find out what compressions method
  103.                     ; that was used.
  104.     move.b    (a3)+,d4        ; d4 will eventually contain 0-15
  105. ;.b -> .w == bättre
  106.     move.w    d4,d5            ; d5, contains count (further count may
  107.     and.b    #$f,d5            ; @ (.w)   be needed for some methods.
  108.     lsr.b    #4,d4            ; The higher 4 bits of d4 is type, and
  109. ;    and.w    #$f,d4            ; the lower count
  110.  
  111. ;    cmpi.b    #2,d4            ; @cmd > 2 then it's a short pattern
  112.     subq.b    #2,d4            ; @subq is faster than cmpi -- we just
  113. ;                    ;  have to adjust two later uses
  114.     bls.s    no_spat            ; (3-15)
  115. ;    move.w    d5,d6            ; count is 3 chars higher actually
  116.     addq.b    #3,d5            ; d5 is never >15+3
  117.     moveq    #0,d7            ; to use d4 as loop-register
  118.     move.b    (a3)+,d7        ; decode offset
  119.     asl.w    #4,d7
  120.     add.w    d5,d7
  121.     move.l    a4,a6            ; Next copy d4 characters from a6
  122.     sub.l    d7,a6            ; to a4
  123. ;    subq.b    #1,d4            ; @
  124. ;                    ; @ This line would get adjusted to
  125. ;                    ;   addq #1 to compensate for subq #2,
  126.     move.b    (a6)+,(a4)+        ; @ but I'll just add one unrolled move
  127. ;                    ;   which does the same thing, faster
  128. ;    ext.w    d4            ; @ since earlier moveq was removed
  129. s_loop    move.b    (a6)+,(a4)+        ;
  130.     dbf    d4,s_loop
  131.     bra.s     mloop            ; Jump to main loop
  132.  
  133.  
  134. no_spat    addq.b    #1,d4            ; @ d4 now equals -1, 0, or 1.  All
  135. ;                    ;   further checks can be made with
  136. ;                                       ;   no more compares needed.
  137.     bpl.s    no_srle            ; @ d4=-1 for srle
  138. ;    addq.b    #2,d5            ; @Remove   cnt += 3 (-1 for dbf loop)
  139.     move.b    (a3)+,d7        ; char to repeat d5 times
  140.     move.b    d7,(a4)+        ; @ Replaced addq.b #2 with two unrolled
  141.     move.b    d7,(a4)+        ;   moves.  2 bytes longer, but faster
  142. sr_loop    move.b    d7,(a4)+        ;   since we save 2 loop iterations
  143.     dbf    d5,sr_loop
  144.     bra.s    mloop            ; Main loop
  145.  
  146.  
  147. no_srle                    ; @ remove cmp #1
  148.     bne.s    no_lrle
  149.     moveq    #0,d7                   ; d4=0 for lrle
  150.     move.b    (a3)+,d7        ; if so, decode high/low count
  151.     asl.w    #4,d7            ; and add them since long RLE
  152.     add.w    d7,d5            ; is least 19 :
  153.  
  154. ;    addi.w    #18,d5            ; @ Remove   cnt +=19 (-1 for dbf loop)
  155.  
  156.     move.b    (a3),d7            ; @ Build d7 to longword size
  157.     lsl.w    #8,d7            ; @
  158.     move.b    (a3)+,d7        ; char to set
  159.     move.w    d7,d4            ; @
  160.     swap    d7            ; @
  161.     move.w    d4,d7            ; @ d7 has chr duplicated in all 4 bytes
  162.     move.w    a4,d4            ; @ Get a4 to an even adr, so we can
  163.     lsr.b    #1,d4            ; @ use move.l's.
  164.     and.b    #$fe,d4
  165.     bcc.s    a4_even            ; @
  166.     move.b    d7,(a4)+        ; @ a4 was odd, so move one odd byte
  167.     subq.w    #1,d5            ; @
  168. a4_even    move.l    d7,(a4)+        ; @ ok, ok, this looks kinda wasteful
  169.     move.l    d7,(a4)+        ; @ Move 18 unrolled bytes to replace
  170.     move.l    d7,(a4)+        ; @ addi.w #18,d5
  171.     move.l    d7,(a4)+        ; @ I wanted this as fast as possible
  172.     move.w    d7,(a4)+        ; @ and I hope no one misses 6 bytes
  173.     move.w    d5,d4            ; @
  174.     and.w    #3,d4            ; @ d4 = d5 modulo 4
  175.     lsr.w    #2,d5            ; @ Adj d5 for move.l loop
  176.     subq.w    #1,d5            ; @
  177.     bmi.s   lr_lp2            ; @ If d5<4
  178. lr_loop    move.l    d7,(a4)+        ; @ (.l)
  179.     dbf    d5,lr_loop
  180. lr_lp2    move.b    d7,(a4)+        ; @ Finish remainder of cnt
  181.     dbf    d4,lr_lp2        ; @
  182.     moveq    #0,d7            ; @ Clear top half of d7 again
  183.     bra.w    mloop            ; @ (.w) Main loop
  184.  
  185.  
  186. no_lrle                    ; only one case left, long pattern
  187.     move.w    d5,d6            ;
  188.     addq.w    #3,d6            ; at least 3 chars long pattern
  189.     moveq    #0,d7
  190.     move.b    (a3)+,d7        ; Decode and add high and low
  191.     asl.w    #4,d7            ; offset
  192.     add.w    d7,d6            ;
  193.     moveq    #0,d5
  194.     move.b    (a3)+,d5        ; Next, get count
  195.     addi.w    #15,d5            ; which is at least 16 (-1 for loop)
  196.     move.l    a4,a6            ; source
  197.     sub.l    d6,a6            ; destination
  198.         lsr.b    #1,d6            ; @ If difference between a6&a4 is odd,
  199.     bcs.s    rl_lp2            ; @ they are not on same boundary
  200.     move.w    a6,d6            ; @ Otherwise, we can opt with move.l
  201. *feppel
  202. ;        lsr.b    #1,d6            ; @
  203.     bcc.s    a6_even            ; @
  204.     move.b    (a6)+,(a4)+        ; @ Move odd byte so both adrs are even
  205.     subq.w    #1,d5            ; @ and adj count
  206. a6_even    move.w    d5,d4            ; @
  207.     and.w    #3,d5            ; @ d5 = d5 modulo 4
  208.     lsr.w    #2,d4            ; @ Adj d4 for move.l loop
  209.     subq.w    #1,d4            ; @
  210. rl_loop    move.l    (a6)+,(a4)+        ; @
  211.     dbf    d4,rl_loop        ; @
  212. rl_lp2    move.b    (a6)+,(a4)+        ; @
  213.     dbf    d5,rl_lp2        ; @
  214.     bra.w    mloop
  215.     END
  216.